package leetcode.editor.cn.q1xx

class Q154 {
    // l == m, in [l,r-1]
    // l <= mid, mid < r [l,r]区间升序, l最小
    // l < mid, mid <= r [l,r]区间升序, l最小
    // l <= mid, mid >= r, min in [mid+1,r]
    // l > mid, min in [l,mid]
    fun findMin(nums: IntArray): Int {
        var l = 0
        var r = nums.size - 1
        while (l < r) {
            val mid = l + (r - l) / 2
            println("$l $r $mid")
            when {
                nums[mid] == nums[r] -> {
                    r--
                }
                nums[mid] < nums[r] -> {
                    r = mid
                }
                else -> {
                    l = mid + 1
                }
            }
        }
        return nums[l]
    }
}

fun main() {
    val sol = Q154()
    val input = intArrayOf(2,1,2,2,2)
    println(sol.findMin(input))
}